Tute (Week 1)

1. Sets and Propositions
2. Logical Reasoning
3. Quantifiers
- 3.1. Question 1
- 3.2. Question 2
4. Proofs
5. Video game proofs

1 Sets and Propositions

Why does the set fact \(A \cap B \subseteq A\) look so much like the propositional fact \(\mathcal{A}\land\mathcal{B}\rightarrow\mathcal{A}\)?

We've seen that intersection \(\cap\) between sets corresponds to \(\land\) between propositions: you are an element of the intersection of two sets, say the set of women and the set of people taller than 1.75m, just if you are a woman and you are taller than 1.75m. Similarly \(\cup\) and \(\lor\) correspond.

In the same vein,

What operator between sets corresponds to \(\Rrightarrow\) between propositions?
What operator between sets corresponds to \(\rightarrow\) between propositions?
What operator between sets corresponds to \(\neg\) on propositions?

\(\Rrightarrow\) corresponds to \(\subseteq\). The former is a binary relation on propositions, in the same way the latter is a relation between sets. \(A \rightarrow B\) can be modelled by \(A^c \cup B\). The third corresponds to complement (\(A^c\)).

2 Logical Reasoning

Assuming that the one-place predicates \(\textsf{even}\), \(\textsf{odd}\) mean "is an even number", "is an odd number" respectively, write general formulae for the following:

Every integer is either even or odd.
Every odd natural number is one more than some even natural number.
There is an even integer that is not one more than any odd natural number.
Zero is the least natural number.
There is no least integer.
Given any positive real number, there is another real number strictly between it and zero.

\(\forall{i\in\mathbb{Z}}.\ {\mathop{\textsf{even}} i \lor\mathop{\textsf{odd}} i}\)
\(\forall{m\in\mathbb{N}}.\ {\mathop{\textsf{odd}} m \rightarrow \exists{n\in\mathbb{N}}.\ {\mathop{\textsf{even}} n \land m=n+1}}\)
\(\exists{i\in\mathbb{Z}}.\ {\mathop{\textsf{even}} i \land \neg \exists{n\in\mathbb{N}}.\ {\mathop{\textsf{odd}} n \land i=n+1}}\)
\(\forall{n\in\mathbb{N}}.\ {0\leq n}\)
\(\neg\exists{i\in\mathbb{Z}}.\ {\forall\ {j\in\mathbb{Z}}.\ {i\leq j}}\)
\(\forall{r\in\mathbb{R}}.\ r>0 \rightarrow\exists{s\in\mathbb{R}}.\ 0 < s < r\)

3 Quantifiers

3.1 Question 1

Recall that \(\exists{x}.\ {\mathcal{A}}\) means "there is at least one \(x\) such that \(\mathcal{A}\)". Write another formula that means "there is at most one \(x\) such that \(\mathcal{A}\)".

\(\exists{y}.\ {\forall{x}.\ {\mathcal{A} \rightarrow x=y}}\).

3.2 Question 2

Now write a formula that means "there is exactly one \(x\) such that \(\mathcal{A}\)".

\(\exists{y}.\ {\forall{x}.\ {\mathcal{A} \leftrightarrow x=y}}\).

4 Proofs

4.1 Question 1

Prove this, using the logical reasoning rules from Appendix E of the IFM book:

\[(\exists{x}.\ {(\mathcal{A} \rightarrow \mathcal{B}) \land (\neg \mathcal{A} \rightarrow \mathcal{C})}) \;\equiv\; (\exists{x}.\ {\mathcal{A} \land \mathcal{B}}) \lor (\exists{x}.\ {\neg \mathcal{A} \land \mathcal{C}}).\]

\begin{array}{clr} & \exists{x}.\ (\mathcal{A} \rightarrow \mathcal{B}) \land (\neg \mathcal{A} \rightarrow \mathcal{C}) & \text{E.42}\\ \equiv & \exists{x}.\ {\mathcal{A} \land \mathcal{B} \lor \neg \mathcal{A} \land {\cal C}} & \text{E.72}\\ \equiv&(\exists{x}.\ {\mathcal{A} \land \mathcal{B}}) \lor (\exists{x}.\ {\neg {\mathcal{A}} \land {\mathcal{C}}})\\ \end{array}

4.2 Question 2

Suppose \(\mathcal{N}\) contains no free \(x\). Prove this: \[\exists{x}.\ {({\mathcal{N}} \rightarrow \mathcal{A}) \land (\neg \mathcal{N} \rightarrow \mathcal{B})}\; \equiv\; (\mathcal{N} \rightarrow \exists{x}.\ {\mathcal{A}}) \land (\neg \mathcal{N} \rightarrow \exists{x}.\ {\mathcal{B}}) \]

Hint: recall the previous question.

\begin{array}{clr} &\exists{x}.\ (\mathcal{N} \rightarrow \mathcal{A}) \land (\neg \mathcal{N} \rightarrow \mathcal{B})&\text{Prev. Question}\\ \equiv & (\exists{x}.\ \mathcal{N} \land \mathcal{A}) \lor (\exists{x}.\ \neg \mathcal{N} \land \mathcal{B})&\text{E.86}\\ \equiv & \mathcal{N} \land (\exists{x}.\ \mathcal{A}) \lor \neg \mathcal{N} \land (\exists{x}.\ {\mathcal{B}})&\text{E.42}\\ \equiv & (\mathcal{N} \rightarrow \exists{x}.\ {\mathcal{A}}) \land (\neg \mathcal{N} \rightarrow \exists{x}.\ {\mathcal{B}}) \end{array}

4.3 Question 3

Show that \[\exists{x,y}.\ {x\neq y} \;\equiv\; \forall{x}.\ {\exists{y}.\ {x\neq y}}\] Hint: To show \({\cal A} \equiv {\cal B}\), show \({\cal A} \Rrightarrow {\cal B}\) and \({\cal B} \Rrightarrow {\cal A}\).

\begin{array}{clr} & \exists{x,y}.\ {x \neq y} & \text{E.80} \\ \equiv & \forall{z}.\ {\exists{x,y}.\ {x\neq y}} & \text{E.13, E.20} \\ \equiv & \forall{z}.\ {\exists{x,y}.\ {(x=z \lor x\neq z) \land x\neq y}} & \text{E.7}\\ \equiv & \forall{z}.\ {\exists{x,y}.\ {x=z \land x\neq y \lor x\neq z \land x\neq y}} & \text{Properties of =} \\ \Rrightarrow & \forall{z}.\ {\exists{x,y}.\ {y\neq z \lor x\neq z}} & \text{E.72}\\ \equiv &\forall{z}.\ {(\exists{x,y}.\ {y\neq z}) \lor (\exists{x,y}.\ {x\neq z})} & \text{E.81} \\ \equiv & \forall{z}.\ {(\exists{y}.\ {y\neq z}) \lor (\exists{x}.\ {x\neq z})}&\text{E.90,E.91}\\ \equiv & \forall{x}.\ {(\exists{y}.\ {y\neq x}) \lor (\exists{y}.\ {y\neq x})}&\text{E.1}\\ \equiv & \forall{x}.\ {\exists{y}.\ {x\neq y}}&\text{E.74}\\ \Rrightarrow & \exists{x,y}.\ {x\neq y}\\ \end{array}

5 Video game proofs

Head over to the incredible proof machine and play the game. By trial and error, you'll pick up the basics of how to do natural deduction proofs, which is something we'll return to later in the course. You don't need to understand the theory behind what you're doing at this point; playing around with it is enough for now.